<?php
//冒泡排序演化
function p($arr){
    return join(',',$arr)."<br>";
}
$arr=[3,1,2,7,5,4,9,0,7,-1,6];
function maopao($arr){
    $len=count($arr);
    for($i=0;$i<$len-1;$i++){
        for($j=$i+1;$j<$len;$j++){
            if($arr[$i]>$arr[$j]){
                $tmp=$arr[$j];
                $arr[$j]=$arr[$i];
                $arr[$i]=$tmp;
            }
        }
    }
    return $arr;

}

/**
 * 3,1,2,7,5,4,9,0,7,-1,6
 * 1,3,2,7,5,4,9,0,7,-1,6
 * 0,3,2,7,5,4,9,1,7,-1,6
 * -1,3,2,7,5,4,9,1,7,0,6
 * 第一轮把0搞到比较靠后的位置
 * 改进
 */

echo p($arr);
echo "<hr>";
echo p(maopao($arr));
//改进版1
function maopao1($arr){
    $len=count($arr);
    for($i=0;$i<$len-1;$i++){
        for($j=$len-1;$j>$i;$j--){
            if($arr[$j]<$arr[$j-1]){
                $tmp=$arr[$j];
                $arr[$j]=$arr[$j-1];
                $arr[$j-1]=$tmp;
            }
        }
    }
    return $arr;
}

/**
 * 3,1,2,7,5,4,9,0,7,-1,6
 * 3,1,2,7,5,4,9,0,-1,7,6
 * 3,1,2,7,5,4,9,-1,0,7,6
 * 3,1,2,7,5,4,-1,9,0,7,6
 * 3,1,2,7,5,-1,4,9,0,7,6
 * 3,1,2,7,-1,5,4,9,0,7,6
 * 3,1,2,-1,7,5,4,9,0,7,6
 * 3,1,-1,2,7,5,4,9,0,7,6
 * 3,-1,1,2,7,5,4,9,0,7,6
 * -1,3,1,2,7,5,4,9,0,7,6
 * -1在往上逐渐冒泡，第一轮排序结束
 * 第1轮:n个元素需要n-1次比较
 * 第2轮:n-1个元素需要n-2次比较
 * 第3轮:n-2个元素需要n-3次比较
 * ............................
 * 第n-1轮:2个元素需要1次比较
 *
 */
echo p(maopao1($arr));
/**
 * 对于有序的
 * 1,2,3,4,5,6
 * 每轮冒泡，记录下是否发生了交换，如果没发生交换，没必要外层循环了
 * 排到每轮不发生冒泡交换为止
 *1,2,3,4,5,6
 * 第一轮的所有交换发现未发生交换行为不再进行外层的了
 *1,2,4,3,5,6
 * 第一轮结束后 1,2,3,4,5,6  发现有交换行为，所以进行下一轮
 * 第二轮介素后发现没发生交换，没必要下一轮了
 *
 *
 */
$arr=[1,2,3,4,5,6];
function maopao2($arr){
    $len=count($arr);
    $swap=true; //比较过程是否交换了
    for($i=0;$i<$len-1 && $swap;$i++){
        $swap=false;
        for($j=$len-1;$j>$i;$j--){
            if($arr[$j]<$arr[$j-1]){
                $tmp=$arr[$j];
                $arr[$j]=$arr[$j-1];
                $arr[$j-1]=$tmp;
                $swap=true;
            }
        }
    }
    return $arr;
}
echo p(maopao2($arr));



















